#include "linearList.h"
#include <iostream>
using namespace std;

//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem-1] << endl;
}



//链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }
        
        
        curNode = curNode->next;
    }
}

sequenceList::sequenceList (const int& maxCap, const int& initLen, float initArr[])
{
    maxCapcity =maxCap; //maxCapcity：顺序表最大容量
    curNumberOfItem = initLen; //curNumberOfItem：当前元素个数
    myList = new float[maxCapcity];
    for (int i = 0; i < initLen; i++) {
        myList[i] = initArr[i];
    }
}

sequenceList::~sequenceList() 
{
    delete[] myList; 
    myList = nullptr; 
}

bool sequenceList::addItem(const float& item){
    if(curNumberOfItem >= maxCapcity) return false;
    myList[curNumberOfItem++] = item;
    return true;
}

bool sequenceList::insertItem(const int& index, const float& item)
{
    if(index < 0 || index > curNumberOfItem || curNumberOfItem >= maxCapcity){
        return false;
    }
    for(int i = curNumberOfItem ; i > index ; i--){
        myList[i] = myList[i-1];
    }
    myList[index] = item;
    curNumberOfItem++;
    return true;
}

int sequenceList::deleteItem(const float& item)
{
    for(int i=0 ; i < curNumberOfItem ; i++){
        if(myList[i] == item){
            for(int y = i ; y < curNumberOfItem ; y++){
                myList[y] = myList[y +1];
            }
            curNumberOfItem--;
            return i;
        }
    }
    return -1;
}

bool sequenceList::locate(const int& index, float& val)
{
    if (index >= 0 && index < curNumberOfItem) {
        val = myList[index];
        return true;
    }
    return false;
}

int sequenceList::locate(const float& item)
 {
    for (int i = 0; i < curNumberOfItem; i++) {
        if (myList[i] == item) return i;
    }
    return -1;
}

void sequenceList::reverse()
{
    int a = 0;
    int b = curNumberOfItem - 1;
    while (a < b) {
        float temp = myList[a];
        myList[a] = myList[b];
        myList[b] = temp;
        a++;
        b--;
    }
}

listNode::listNode(float nodeData, listNode* succ) {
    data = nodeData;
    next = succ;
}
listNode::~listNode() {}

linkList::linkList(const int& initLen, float initArr[]) {
    firstNode = new listNode(0); 
    lastNode = firstNode; 
    listSize = 0;
    for (int i = 0; i < initLen; i++) {
        tailInsertItem(initArr[i]);//尾插法 从尾部插入元素
    }
}

linkList::linkList() {
    firstNode = new listNode(0);
    lastNode = firstNode;
    listSize = 0;
}

bool linkList::headInsertItem(const float& item)
{
    listNode* newNode = new listNode(item, firstNode->next);
    firstNode->next = newNode;
    
    if(listSize == 0)
    {
        lastNode = newNode;
    }
    
    listSize++;
    return true;
}

bool linkList::tailInsertItem(const float& item)
{
    listNode* newNode = new listNode(item);
    lastNode->next = newNode;
    lastNode = newNode;
    listSize++;
    return true;
}

int linkList::insertItem(const int& index, const float& item)
{
    if(index < 0 || index > listSize)
        return -1;
    listNode* current = firstNode;
    for(int i = 0; i < index; i++)
    {
        current = current->next;
    }
    listNode* newNode = new listNode(item, current->next);
    current->next = newNode;
    if(index == listSize)
    {
        lastNode = newNode;
    }
    listSize++;
    return index;
}

int linkList::deleteItem(const float& item)
{
    listNode* current = firstNode;
    int a = 0;
    while(current->next != NULL){
        if(current->next->data == item){
            listNode* temp = current->next;
            current->next = temp->next;
            if(temp == lastNode)
            {
                lastNode = current;
            }
            delete temp;
            listSize--;
            return a;
        }
    current = current->next;
    a++;
    }
    return -1;
}

bool linkList::locate(const int& index, float& val)
{
    if(index < 0 || index >= listSize) return false;
    listNode* current = firstNode->next;
    for(int i = 0; i < index; i++){
        current = current->next;
    }
    val = current->data;
    return true;
}

int linkList::locate(const float& item)
{
    listNode* current = firstNode->next;
    int a = 0;
    while(current != NULL)
    {
        if(current->data == item)
            return a;
        current = current->next;
        a++;
    }
    return -1;
}

void linkList::ascendingOrder()
{
    if(listSize <= 1) return;
    for(listNode* i = firstNode->next; i->next != NULL; i = i->next){
        listNode* min = i;
        for(listNode* j = i->next; j != NULL; j = j->next)
        {
            if(j->data < min->data)
            {
                min = j;
            }
        }
        if(min != i){
            float temp = i->data;
            i->data = min->data;
            min->data =temp;
        }
    }
}

void linkList::reverse()
{
    if(listSize <= 1) return;
    listNode* p = NULL;
    listNode* current = firstNode->next;
    listNode* q = NULL;
    lastNode = current; 
    while(current != NULL){
        q = current->next;
        current->next = p;
        p = current;
        current = q;
    }
    firstNode->next = p;
}
 
linkList::~linkList()
{
    listNode* current = firstNode;
    while(current != NULL)
    {
        listNode* temp = current;
        current = current->next;
        delete temp;
    }
}

void merge(linkList& A, linkList& B)
{
    A.ascendingOrder();
    B.ascendingOrder();
    
    listNode* headA = A.firstNode->next;
    listNode* headB = B.firstNode->next;
    listNode* mergedHead = NULL;
    
    while(headA != NULL && headB != NULL)
    {
        if(headA->data <= headB->data)
        {
            listNode* temp = headA->next;
            headA->next = mergedHead;
            mergedHead = headA;
            headA = temp;
        }
        else
        {
            listNode* temp = headB->next;
            headB->next = mergedHead;
            mergedHead = headB;
            headB = temp;
        }
    }
    
    while(headA != NULL)
    {
        listNode* temp = headA->next;
        headA->next = mergedHead;
        mergedHead = headA;
        headA = temp;
    }
    
    while(headB != NULL)
    {
        listNode* temp = headB->next;
        headB->next = mergedHead;
        mergedHead = headB;
        headB = temp;
    }
    
    A.firstNode->next = mergedHead;
    A.listSize += B.listSize;
    
    listNode* current = mergedHead;
    while(current != NULL && current->next != NULL)
    {
        current = current->next;
    }
    A.lastNode = current;
    
    B.firstNode->next = NULL;
    B.lastNode = B.firstNode;
    B.listSize = 0;
}